import sun.reflect.generics.tree.Tree;

import java.util.HashMap;

public class Test06 {
    public static HashMap<Integer,Integer> map = new HashMap();
    public static void main(String[] args) {
        //普通
        int[] preorder = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] inorder = {4, 7, 2, 1, 5, 3, 8, 6};
        for(int i = 0; i< inorder.length ;i++){
            map.put(inorder[i],i);
        }
        TreeNode construct = construct(preorder, inorder);
        inorderTree(construct);
        map.clear();//清空map
        System.out.println();
        //没有右子树
        int[] preorder1 = {1, 2, 3, 4, 5};
        int[] inorder1 = {5, 4, 3, 2, 1};
        for(int i = 0; i< inorder1.length ;i++){
            map.put(inorder1[i],i);
        }
        TreeNode construct1 = construct(preorder1, inorder1);
        inorderTree(construct1);
    }

    public static TreeNode construct(int[] preorder, int[] inorder) {
        // 输入的合法性判断，两个数组都不能为空，并且都有数据，而且数据的数目相同
        if (preorder == null || inorder == null || preorder.length != inorder.length || inorder.length < 1) {
            return null;
        }

        return construct(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    public static TreeNode construct(int[] pre,int prestart,int preend,int[] in,int instart,int inend){
        if (prestart > preend) return null;
        TreeNode root = new TreeNode(pre[prestart]);//前序遍历的第一个点为根节点
        int index = map.get(pre[prestart]);//找到根结点的下标
        root.left = construct(pre,prestart+1,prestart+index-instart,in,instart,index-1);
        root.right = construct(pre,prestart+index-instart+1,preend,in,index+1,inend);
        return root;
    }
    public static void inorderTree(TreeNode treeNode){
        if (treeNode != null){
            inorderTree(treeNode.left);
            System.out.print(treeNode.val +" ");
            inorderTree(treeNode.right);
        }
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
